package day51_688;

/**
 * @ClassName Solution
 * @Description TODO
 * @Author clockTown
 * @Date 2021/6/29 19:13
 * @Version 1.0
 */
public class Solution {
    public double knightProbability(int n, int k, int row, int column) {
        //存储当前棋盘上对应位置有马的概率
        double[][] dp = new double[n][n];
        int[] dr = new int[]{-2, -2, -1, -1, 1, 1, 2, 2};
        int[] dc = new int[]{-1, 1, -2, 2, -2, 2, -1, 1};

        dp[row][column] = 1;
        for (; k > 0; k--) {
            //存储最新的概率
            double[][] dpTemp = new double[n][n];
            for (int r = 0; r < n; r++) {
                for (int c = 0; c < n; c++) {
                    for (int j = 0; j < 8; j++) {
                        int newRow = r + dr[j];
                        int newColumn = c + dc[j];
                        if (newRow >= 0 && newRow < n || newColumn >= 0 && newColumn < n){
                            dpTemp[row][column] += dp[newRow][newColumn] * 0.125;
                        }

                    }
                }
            }
        //将最新的概率数组覆盖到当前概率数组上
        dp = dpTemp;
        }
        double res = 0;
        //遍历获得总的概率
        for (int i = 0; i < n; i++){
            for (int j = 0; j < n; j++) {
                res += dp[i][j];
            }
        }
        return res;
    }
}
